<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<script src="jquery.js"> </script>
</head>
<body>
<p> 请在下面的输入框中输入价格。直接输入数字即可，使用空格分割。建议商品数量在 16 个以内	 </p>
<input id="input" size="100" value="10 20 280 290"></input> <br />
<button id="submit">提交</button>
<br />

<p id="answer">
结果: <br />
总花费：<span id="finalCost"></span> <br />
扣 40 次数：<span id="finalReduce"></span> <br />
划分方式：<span id="finalWay"></span>
</p>

<p id="about">
作者：intlsy
</p>

<script>

function Calculate(){
	a = $("#input")[0].value.split(" ")
	n = a.length
	for( var i = 0 ; i < n ; ++i )
		a[i] = parseFloat(a[i])
	console.log(a)
	
	sum = new Array(1<<n)
	sum[0] = 0
	for( var i = 1 ; i < (1<<n) ; ++i )
		for( var j = 0 ; j < n ; ++j )
			if( (i>>j&1) ){
				sum[i] = sum[i^(1<<j)] + a[j]
				break
			}
	console.log(sum)
	
	mem = new Array(1<<n)
	trans = new Array(1<<n)
	function Dfs(mask){
		if( mask == (1<<n)-1 ) return 0;
		if( mem[mask] != undefined ) return mem[mask];
		var umask = ((1<<n)-1) ^ mask
		
		var ans = sum[umask]
		var ansSub = umask
		for( var s = umask ; s ; s = (s-1)&umask ){
			if( sum[s] < 299.999 ) continue;
			var tans = Dfs(mask|s) + sum[s] - 40;
			if( ans > tans ){
				ans = tans;
				ansSub = s;
			}
		}
		mem[mask] = ans
		trans[mask] = ansSub
		return ans
	}
	
	var finalCost = Math.round(Dfs(0)*100) / 100
	console.log(finalCost)
	$("#finalCost").text(finalCost)
	
	var finalReduce = Math.round((sum[(1<<n)-1]-finalCost)/40);
	console.log(finalReduce)
	$("#finalReduce").text(finalReduce)
	
	var finalWay = "";
	var nowMask = 0;
	while( nowMask != (1<<n)-1 ){
		var nowSub = trans[nowMask]
		for( var i = 0 ; i < n ; ++i )
			if( nowSub>>i&1 )
				finalWay += String(a[i]) + " "
		finalWay += "  |  "
		nowMask |= nowSub
	}
	console.log(finalWay)
	$("#finalWay").text(finalWay)
}

$("#submit").click(function(){Calculate()})
</script>

</body>
</html>
